﻿/*
Digraph (library for building, traversal, comparison and saving of directed
graph).

Copyright (C) 2014 Dmitry Merzagitovich Arslanov

This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free
Software Foundation; either version 2.1 of the License, or (at your option) any
later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
*/

namespace CustomTypes
{
    using System;
    using System.ComponentModel;
    using System.Globalization;

    [TypeConverter(typeof(NodeConverter))]
    public class Node
    {
        public string Name { get; set; }

        public double Value { get; set; }

        public Node(string name, double value)
        {
            Name = name;
            Value = value;
        }
    }

    public class NodeConverter : TypeConverter
    {
        public override bool CanConvertTo(ITypeDescriptorContext context,
                                          Type destinationType)
        {
            return destinationType == typeof(string);
        }

        public override bool CanConvertFrom(ITypeDescriptorContext context,
                                            Type sourceType)
        {
            return sourceType == typeof(string);
        }

        public override object ConvertFrom(ITypeDescriptorContext context,
                                           CultureInfo culture,
                                           object value)
        {
            string str = value as string;
            string[] records = str.Split(';');
            string nodeName = string.Empty;
            double nodeValue = 0.0;
            foreach (string record in records)
            {
                string[] args = record.Split('=');
                if (string.IsNullOrEmpty(nodeName)) nodeName = args[1];
                else nodeValue = double.Parse(args[1]);
            }
            return new Node(nodeName, nodeValue);
        }

        public override object ConvertTo(ITypeDescriptorContext context,
                                         CultureInfo culture,
                                         object value,
                                         Type destinationType)
        {
            Node node = value as Node;
            return string.Format("Name={0};Value={1}", node.Name, node.Value);
        }
    }
}

namespace DigraphUnitTest
{
    using CustomTypes;
    using Microsoft.VisualStudio.TestTools.UnitTesting;
    using System;
    using System.Collections.Generic;
    using System.Windows;

    using DigraphVertex = Digraph.Vertex<string, string>;
    using DigraphSet = Digraph.Set<string, string>;
    using DigraphArc = Digraph.Arc<string, string>;
    using DigraphBuilder = Digraph.Builder<string, string>;
    using DigraphDiff = Digraph.Difference<string, string>;
    using DigraphPath = Digraph.Path<string, string>;

    using Builder = Digraph.Builder<CustomTypes.Node, System.Windows.Vector>;
    using Vertex = Digraph.Vertex<CustomTypes.Node, System.Windows.Vector>;

    [TestClass]
    public class TestSet
    {
        [TestMethod]
        public void Creation()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphSet g = b.Digraph;

            Assert.IsTrue(g.Vertices.Contains(v1),
                "Digraph does not contain vertex # 1.");
            Assert.IsTrue(g.Vertices.Contains(v2),
                "Digraph does not contain vertex # 2.");
            Assert.IsTrue(g.Arcs.Contains(a1),
                "Digraph does not contain arc between vertex # 1 and # 2.");
            Assert.IsTrue(v1.OutcomingArcs.Contains(a1),
             "Outcoming arcs of vertex # 1 do not contain arc to vertex # 2.");
            Assert.IsTrue(v2.IncomingArcs.Contains(a1),
            "Incoming arcs of vertex # 2 do not contain arc from vertex # 1.");
            Assert.AreSame(a1.FromVertex, v1,
                "Vertex # 1 of arc is incorrect.");
            Assert.AreSame(a1.ToVertex, v2,
                "Vertex # 2 of arc is incorrect.");
            Assert.AreEqual(v1.Content, "v1", "Incorrect data of vertex # 1.");
            Assert.AreEqual(v2.Content, "v2", "Incorrect data of vertex # 2.");
            Assert.AreEqual(a1.Content, "a1",
                "Incorrect data of arc between vertex # 1 and # 2.");
        }

        [TestMethod]
        public void VertexDeleting()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            b.DeleteVertex(v2);
            DigraphSet g = b.Digraph;

            Assert.IsTrue(g.Vertices.Contains(v1),
                "Digraph does not contain vertex # 1.");
            Assert.IsTrue(!g.Vertices.Contains(v2),
                "Digraph contains vertex # 2.");
            Assert.AreEqual(g.Arcs.Count, 0,
                "Digraph contains arc between vertex # 1 and # 2.");
            Assert.AreEqual(v1.OutcomingArcs.Count, 0,
             "Outcoming arcs of vertex # 1 contain arc to vertex # 2.");
            Assert.AreEqual(v2.IncomingArcs.Count, 0,
            "Incoming arcs of vertex # 2 contain arc from vertex # 1.");
            Assert.IsNull(a1.FromVertex, "Vertex # 1 of arc is incorrect.");
            Assert.IsNull(a1.ToVertex, "Vertex # 2 of arc is incorrect.");
        }

        [TestMethod]
        public void ArcDeleting()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            b.DeleteArc(a1);
            DigraphSet g = b.Digraph;

            Assert.IsTrue(g.Vertices.Contains(v1),
                "Digraph does not contain vertex # 1.");
            Assert.IsTrue(g.Vertices.Contains(v2),
                "Digraph does not contain vertex # 2.");
            Assert.AreEqual(g.Arcs.Count, 0,
                "Digraph contains arc between vertex # 1 and # 2.");
            Assert.AreEqual(v1.OutcomingArcs.Count, 0,
              "Outcoming arcs of vertex # 1 contain arc to vertex # 2.");
            Assert.AreEqual(v2.IncomingArcs.Count, 0,
            "Incoming arcs of vertex # 2 contain arc from vertex # 1.");
            Assert.IsNull(a1.FromVertex, "Vertex # 1 of arc is incorrect.");
            Assert.IsNull(a1.ToVertex, "Vertex # 2 of arc is incorrect.");
        }

        [TestMethod]
        public void Saving()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphSet g = b.Digraph;
            string tgf = g.ToString();

            Assert.AreEqual(tgf, "1 v1" + Environment.NewLine +
                                 "2 v2" + Environment.NewLine +
                                 "#" + Environment.NewLine +
                                 "1 2 a1" + Environment.NewLine,
                                 "Error in tgf saving.");
        }

        [TestMethod]
        public void Loading()
        {
            string tgf = "1 v1" + Environment.NewLine +
                         "2 v2" + Environment.NewLine +
                         "#" + Environment.NewLine +
                         "1 2 a1";
            DigraphBuilder b = DigraphBuilder.Parse(tgf);
            DigraphSet g = b.Digraph;
            DigraphVertex v1 = g.Vertices[0];
            DigraphVertex v2 = g.Vertices[1];
            DigraphArc a1 = g.Arcs[0];

            Assert.IsTrue(g.Vertices.Contains(v1),
                "Digraph does not contain vertex # 1.");
            Assert.IsTrue(g.Vertices.Contains(v2),
                "Digraph does not contain vertex # 2.");
            Assert.IsTrue(g.Arcs.Contains(a1),
                "Digraph does not contain arc between vertex # 1 and # 2.");
            Assert.IsTrue(v1.OutcomingArcs.Contains(a1),
             "Outcoming arcs of vertex # 1 do not contain arc to vertex # 2.");
            Assert.IsTrue(v2.IncomingArcs.Contains(a1),
            "Incoming arcs of vertex # 2 do not contain arc from vertex # 1.");
            Assert.AreSame(a1.FromVertex, v1,
                "Vertex # 1 of arc is incorrect.");
            Assert.AreSame(a1.ToVertex, v2,
                "Vertex # 2 of arc is incorrect.");
            Assert.AreEqual(v1.Content, "v1", "Incorrect data of vertex # 1.");
            Assert.AreEqual(v2.Content, "v2", "Incorrect data of vertex # 2.");
            Assert.AreEqual(a1.Content, "a1",
                "Incorrect data of arc between vertex # 1 and # 2.");
        }

        [TestMethod]
        public void VerticesAreEquals()
        {
            DigraphBuilder b1 = new DigraphBuilder();
            DigraphVertex g1v1 = b1.NewVertex("v1");
            DigraphVertex g1v2 = b1.NewVertex("v2");
            DigraphArc g1a1 = b1.NewArc(g1v1, g1v2, "a1");

            DigraphBuilder b2 = new DigraphBuilder();
            DigraphVertex g2v1 = b2.NewVertex("v1");
            DigraphVertex g2v2 = b2.NewVertex("v2");
            DigraphArc g2a1 = b2.NewArc(g2v1, g2v2, "a1");

            Assert.AreEqual(g1v1, g2v1, "Vertices are not equals.");
        }

        [TestMethod]
        public void ArcAreEquals()
        {
            DigraphBuilder b1 = new DigraphBuilder();
            DigraphVertex g1v1 = b1.NewVertex("v1");
            DigraphVertex g1v2 = b1.NewVertex("v2");
            DigraphArc g1a1 = b1.NewArc(g1v1, g1v2, "a1");

            DigraphBuilder b2 = new DigraphBuilder();
            DigraphVertex g2v1 = b2.NewVertex("v1");
            DigraphVertex g2v2 = b2.NewVertex("v2");
            DigraphArc g2a1 = b2.NewArc(g2v1, g2v2, "a1");

            Assert.AreEqual(g1a1, g2a1, "Arcs are not equals.");
        }

        [TestMethod]
        public void Difference()
        {
            DigraphBuilder b1 = new DigraphBuilder();
            DigraphVertex g1v1 = b1.NewVertex("v1");
            DigraphVertex g1v2 = b1.NewVertex("v2");
            DigraphVertex g1v3 = b1.NewVertex("v3");
            DigraphArc g1a1 = b1.NewArc(g1v1, g1v2, "a1");
            DigraphArc g1a2 = b1.NewArc(g1v1, g1v3, "a2");
            DigraphSet g1 = b1.Digraph;

            DigraphBuilder b2 = new DigraphBuilder();
            DigraphVertex g2v1 = b2.NewVertex("v1");
            DigraphVertex g2v2 = b2.NewVertex("v2");
            DigraphVertex g2v4 = b2.NewVertex("v4");
            DigraphArc g2a1 = b2.NewArc(g2v1, g2v2, "a1");
            DigraphArc g2a4 = b2.NewArc(g2v1, g2v4, "a4");
            DigraphSet g2 = b2.Digraph;

            DigraphDiff d = DigraphSet.Compare(g1, g2);

            Assert.IsTrue(d.AddedVertices.Contains(g2v4),
                "Added vertex error.");
            Assert.IsTrue(d.AddedArcs.Contains(g2a4),
                "Added arc error.");
            Assert.IsTrue(d.RemovedVertices.Contains(g1v3),
                "Removed vertex error.");
            Assert.IsTrue(d.RemovedArcs.Contains(g1a2),
                "Removed arc error.");
        }

        [TestMethod]
        public void Sources()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphSet g = b.Digraph;
            List<DigraphVertex> s = g.GetSources();
            Assert.IsTrue(s.Contains(v1), "Sources detection error.");
        }

        [TestMethod]
        public void Sinks()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphSet g = b.Digraph;
            List<DigraphVertex> s = g.GetSinks();
            Assert.IsTrue(s.Contains(v2), "Sinks detection error.");
        }

        [TestMethod]
        public void Isolated()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphVertex v3 = b.NewVertex("v3");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphSet g = b.Digraph;
            List<DigraphVertex> i = g.GetIsolatedVertices();
            Assert.IsTrue(i.Contains(v3), "Isolated detection error.");
        }

        [TestMethod]
        public void Pathes()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphVertex v3 = b.NewVertex("v3");
            DigraphVertex v4 = b.NewVertex("v4");
            DigraphVertex v5 = b.NewVertex("v5");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphArc a2 = b.NewArc(v2, v3, "a2");
            DigraphArc a3 = b.NewArc(v2, v4, "a3");
            DigraphArc a4 = b.NewArc(v4, v2, "a4");
            DigraphSet g = b.Digraph;
            List<DigraphPath> pathes = g.GetPathes();
            string[] strs = new string[3];
            Assert.AreEqual(pathes.Count, 3, "Wrong path number.");
            for (int i = 0; i < pathes.Count; i++)
            {
                strs[i] = pathes[i][0].Content;
                for (int j = 1; j < pathes[i].Count; j++)
                {
                    strs[i] += " " + pathes[i][j].Content;
                }
            }
            Assert.AreEqual(strs[0], "a1 a2", "Wrong path.");
            Assert.AreEqual(strs[1], "a1 a3 a4 a2", "Wrong path.");
            Assert.AreEqual(strs[2], "a1 a3 a4 a3", "Wrong path.");
        }

        [TestMethod]
        public void MinPath()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphVertex v3 = b.NewVertex("v3");
            DigraphVertex v4 = b.NewVertex("v4");
            DigraphVertex v5 = b.NewVertex("v5");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphArc a2 = b.NewArc(v2, v3, "a2");
            DigraphArc a3 = b.NewArc(v2, v4, "a3");
            DigraphArc a4 = b.NewArc(v4, v2, "a4");
            DigraphSet g = b.Digraph;
            DigraphPath path = g.GetMinimumPath(v1, v3, arc => 1.0);
            string str = path[0].Content;
            for (int i = 1; i < path.Count; i++)
            {
                str += " " + path[i].Content;
            }
            Assert.AreEqual(str, "a1 a2", "Wrong path.");
        }

        [TestMethod]
        public void ForEach()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphVertex v3 = b.NewVertex("v3");
            DigraphVertex v4 = b.NewVertex("v4");
            DigraphVertex v5 = b.NewVertex("v5");
            DigraphVertex v6 = b.NewVertex("v6");
            DigraphVertex v7 = b.NewVertex("v7");
            DigraphVertex v8 = b.NewVertex("v8");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphArc a2 = b.NewArc(v1, v3, "a2");
            DigraphArc a3 = b.NewArc(v2, v4, "a3");
            DigraphArc a4 = b.NewArc(v2, v5, "a4");
            DigraphArc a5 = b.NewArc(v2, v6, "a5");
            DigraphArc a6 = b.NewArc(v3, v7, "a6");
            DigraphSet g = b.Digraph;
            string trace = string.Empty;
            g.ForEachVertex(false, true, v => trace += v.Content + " ");
            Assert.AreEqual(trace, "v8 v1 v2 v3 v4 v5 v6 v7 ",
                "Wrong foreach trace from sources in width.");
            trace = string.Empty;
            g.ForEachVertex(false, false, v => trace += v.Content + " ");
            Assert.AreEqual(trace, "v8 v1 v2 v4 v5 v6 v3 v7 ",
                "Wrong foreach trace from sources in depth.");
            trace = string.Empty;
            g.ForEachVertex(true, true, v => trace += v.Content + " ");
            Assert.AreEqual(trace, "v8 v4 v5 v6 v7 v2 v3 v1 ",
                "Wrong foreach trace from sinks in width.");
            trace = string.Empty;
            g.ForEachVertex(true, false, v => trace += v.Content + " ");
            Assert.AreEqual(trace, "v8 v4 v2 v1 v5 v6 v7 v3 ",
                "Wrong foreach trace from sinks in depth.");
        }

        [TestMethod]
        public void Traverse()
        {
            DigraphBuilder b = new DigraphBuilder();
            DigraphVertex v1 = b.NewVertex("v1");
            DigraphVertex v2 = b.NewVertex("v2");
            DigraphVertex v3 = b.NewVertex("v3");
            DigraphVertex v4 = b.NewVertex("v4");
            DigraphArc a1 = b.NewArc(v1, v2, "a1");
            DigraphArc a2 = b.NewArc(v2, v3, "a2");
            DigraphSet g = b.Digraph;
            string trace = string.Empty;
            List<DigraphVertex> vxs = new List<DigraphVertex>();
            vxs.Add(v1);
            g.Traverse(v1, Digraph.Direction.Both,
                (pv, cv) =>
                {
                    if (vxs.Contains(cv)) return pv;
                    vxs.Add(cv);
                    return cv;
                },
                v => trace += (v != null ? v.Content : "null") + " ");
            Assert.AreEqual(trace, "v2 v3 null ", "Wrong trace.");
        }

        [TestMethod]
        public void SaveAndLoadBack()
        {
            Builder builder = new Builder();
            Vertex v1 = builder.NewVertex(new Node("v1", 1.0));
            Vertex v2 = builder.NewVertex(new Node("v2", 2.0));
            Vertex v3 = builder.NewVertex(new Node("v3", 3.0));
            builder.NewArc(v1, v2, new Vector(1.0, 0.0));
            builder.NewArc(v2, v3, new Vector(0.0, 1.0));
            builder.Digraph.Save("digraph.tgf");
            Builder loadedBuilder = Builder.Load("digraph.tgf");
            Assert.AreEqual(builder.Digraph.ToString(),
                            loadedBuilder.Digraph.ToString(),
                            "Error in save and back loading.");
        }
    }
}
